package com.yww.datastructure.priorityqueue;

import com.yww.datastructure.queue.Queue;

import java.util.Iterator;

/**
 * @author yww
 * @description 有序数组实现优先队列，入队使用一次插入排序
 * @since 2024/2/6 10:11
 */
@SuppressWarnings("unchecked")
public final class PriorityQueue2<E extends Priority> implements Queue<E> {
    private final Priority[] array;
    private int size;

    public PriorityQueue2(int capacity) {
        this.array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        // 入队保持有序，使用一次插入排序
        int index = size - 1;
        while (index >= 0 && array[index].priority() > value.priority()) {
            // index上元素大于插入元素，index元素后移
            array[index + 1] = array[index];
            index--;
        }
        // 将元素插入
        array[index + 1] = value;
        size++;
        return true;
    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Priority tail = array[size - 1];
        array[size - 1] = null; // help gc
        size--;
        return (E) tail;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = size - 1;

            @Override
            public boolean hasNext() {
                return p >= 0;
            }

            @Override
            public E next() {
                return (E) array[p--];
            }
        };
    }
}
